0855. 考场就座【中等】
1. 📝 题目描述
在考场里，有 n 个座位排成一行，编号为 0 到 n - 1。
当学生进入考场后，他必须坐在离最近的人最远的座位上。如果有多个这样的座位，他会坐在编号最小的座位上。(另外，如果考场里没有人，那么学生就坐在 0 号座位上。)
设计一个模拟所述考场的类。
实现 ExamRoom 类：
ExamRoom(int n)用座位的数量n初始化考场对象。int seat()返回下一个学生将会入座的座位编号。void leave(int p)指定坐在座位p的学生将离开教室。保证座位p上会有一位学生。
示例 1：
txt
输入：
["ExamRoom", "seat", "seat", "seat", "seat", "leave", "seat"]
[[10], [], [], [], [], [4], []]
输出：
[null, 0, 9, 4, 2, null, 5]
解释：
ExamRoom examRoom = new ExamRoom(10);
examRoom.seat(); // 返回 0，房间里没有人，学生坐在 0 号座位。
examRoom.seat(); // 返回 9，学生最后坐在 9 号座位。
examRoom.seat(); // 返回 4，学生最后坐在 4 号座位。
examRoom.seat(); // 返回 2，学生最后坐在 2 号座位。
examRoom.leave(4);
examRoom.seat(); // 返回 5，学生最后坐在 5 号座位。1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
提示：
1 <= n <= 10^9- 保证有学生正坐在座位
p上。 seat和leave最多被调用10^4次。
2. 🎯 s.1 - 有序集合
c
typedef struct {
int* seats;
int size;
int n;
} ExamRoom;
ExamRoom* examRoomCreate(int n) {
ExamRoom* obj = (ExamRoom*)malloc(sizeof(ExamRoom));
obj->seats = (int*)malloc(sizeof(int) * n);
obj->size = 0;
obj->n = n;
return obj;
}
int examRoomSeat(ExamRoom* obj) {
if (obj->size == 0) { obj->seats[obj->size++] = 0; return 0; }
int maxDist = obj->seats[0], best = 0;
for (int i = 1; i < obj->size; i++) {
int d = (obj->seats[i] - obj->seats[i - 1]) / 2;
if (d > maxDist) { maxDist = d; best = obj->seats[i - 1] + d; }
}
if (obj->n - 1 - obj->seats[obj->size - 1] > maxDist) best = obj->n - 1;
int idx = obj->size;
for (int i = 0; i < obj->size; i++) { if (obj->seats[i] > best) { idx = i; break; } }
memmove(obj->seats + idx + 1, obj->seats + idx, sizeof(int) * (obj->size - idx));
obj->seats[idx] = best;
obj->size++;
return best;
}
void examRoomLeave(ExamRoom* obj, int p) {
int idx = 0;
for (int i = 0; i < obj->size; i++) { if (obj->seats[i] == p) { idx = i; break; } }
memmove(obj->seats + idx, obj->seats + idx + 1, sizeof(int) * (obj->size - idx - 1));
obj->size--;
}
void examRoomFree(ExamRoom* obj) { free(obj->seats); free(obj); }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
js
/**
* @param {number} n
*/
var ExamRoom = function (n) {
this.n = n
this.seats = []
}
/**
* @return {number}
*/
ExamRoom.prototype.seat = function () {
if (this.seats.length === 0) {
this.seats.push(0)
return 0
}
let maxDist = this.seats[0],
best = 0
for (let i = 1; i < this.seats.length; i++) {
const d = Math.floor((this.seats[i] - this.seats[i - 1]) / 2)
if (d > maxDist) {
maxDist = d
best = this.seats[i - 1] + d
}
}
if (this.n - 1 - this.seats[this.seats.length - 1] > maxDist)
best = this.n - 1
const idx = this.seats.findIndex((s) => s > best)
if (idx === -1) this.seats.push(best)
else this.seats.splice(idx, 0, best)
return best
}
/**
* @param {number} p
* @return {void}
*/
ExamRoom.prototype.leave = function (p) {
const idx = this.seats.indexOf(p)
this.seats.splice(idx, 1)
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
py
class ExamRoom:
def __init__(self, n: int):
self.n = n
self.seats = []
def seat(self) -> int:
if not self.seats:
self.seats.append(0)
return 0
max_dist = self.seats[0]
best = 0
for i in range(1, len(self.seats)):
d = (self.seats[i] - self.seats[i - 1]) // 2
if d > max_dist:
max_dist = d
best = self.seats[i - 1] + d
if self.n - 1 - self.seats[-1] > max_dist:
best = self.n - 1
import bisect
bisect.insort(self.seats, best)
return best
def leave(self, p: int) -> None:
self.seats.remove(p)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
- 时间复杂度：
seatleave - 空间复杂度：
算法思路：
- 维护有序座位列表，
seat时遍历相邻已占座位的间距找最大距离点 - 特殊处理左端和右端的空位，插入时保持有序